// 版权所有2009年围棋作者。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package types

import (
	"bytes"
	"fmt"
	"sort"

	"cmd/compile/internal/base"
	"cmd/internal/src"
)

var PtrSize int

var RegSize int

// 运行时中的切片由三个组件表示：
// None
// 类型切片结构{
// 指针
// 莱恩内特酒店
// cap int
// }
// None
// 运行时中的字符串由两个组件表示：
// None
// 类型字符串结构{
// 指针
// 莱恩内特酒店
// }
// None
// 这些变量是字段的偏移量和这些结构的大小。
var (
	SlicePtrOffset int64
	SliceLenOffset int64
	SliceCapOffset int64

	SliceSize  int64
	StringSize int64
)

var SkipSizeForTracing bool

// typePos返回与t关联的位置。
// 这是t被声明或作为类型表达式出现的地方。
func typePos(t *Type) src.XPos {
	if pos := t.Pos(); pos.IsKnown() {
		return pos
	}
	base.Fatalf("bad type: %v", t)
	panic("unreachable")
}

// MaxWidth是目标体系结构上值的最大大小。
var MaxWidth int64

// CalcSizeDisabled表示它是否安全
// 计算类型的宽度和路线。见CalcSize。
var CalcSizeDisabled bool

// 机器尺寸和成圆对齐由周围指定
// 指针的大小，在betypeinit中设置（请参阅../amd64/galign.go）。
var defercalc int

func Rnd(o int64, r int64) int64 {
	if r < 1 || r > 8 || r&(r-1) != 0 {
		base.Fatalf("rnd %d", r)
	}
	return (o + r - 1) &^ (r - 1)
}

// expandiface通过以下方式计算接口类型t的方法集：
// 扩展嵌入式接口。
func expandiface(t *Type) {
	seen := make(map[*Sym]*Field)
	var methods []*Field

	addMethod := func(m *Field, explicit bool) {
		switch prev := seen[m.Sym]; {
		case prev == nil:
			seen[m.Sym] = m
		case AllowsGoVersion(t.Pkg(), 1, 14) && !explicit && Identical(m.Type, prev.Type):
			return
		default:
			base.ErrorfAt(m.Pos, "duplicate method %s", m.Sym.Name)
		}
		methods = append(methods, m)
	}

	for _, m := range t.Methods().Slice() {
		if m.Sym == nil {
			continue
		}

		CheckSize(m.Type)
		addMethod(m, true)
	}

	for _, m := range t.Methods().Slice() {
		if m.Sym != nil || m.Type == nil {
			continue
		}

		if !m.Type.IsInterface() {
			base.ErrorfAt(m.Pos, "interface contains embedded non-interface %v", m.Type)
			m.SetBroke(true)
			t.SetBroke(true)
			// 添加到字段，以便显示错误消息
			// 如果需要，请包含断开的嵌入类型
			// 印刷t。
			// TODO（mdempsky）：重新审视这一点。
			methods = append(methods, m)
			continue
		}

		// 嵌入式接口：复制所有方法
		// （包括破损的，如有）并添加到t
		// 方法集。
		for _, t1 := range m.Type.AllMethods().Slice() {
			// 使用m.Pos而不是t1.Pos来保持嵌入位置。
			f := NewField(m.Pos, t1.Sym, t1.Type)
			addMethod(f, false)
		}
	}

	sort.Sort(MethodsByName(methods))

	if int64(len(methods)) >= MaxWidth/int64(PtrSize) {
		base.ErrorfAt(typePos(t), "interface too large")
	}
	for i, m := range methods {
		m.Offset = int64(i) * int64(PtrSize)
	}

	t.SetAllMethods(methods)
}

func calcStructOffset(errtype *Type, t *Type, o int64, flag int) int64 {
	// 标志为0（接收器）、1（实际结构）或RegSize（输入/输出参数）
	isStruct := flag == 1
	starto := o
	maxalign := int32(flag)
	if maxalign < 1 {
		maxalign = 1
	}
	lastzero := int64(0)
	for _, f := range t.Fields().Slice() {
		if f.Type == nil {
			// 断开的字段，只需跳过它，以便其他有效字段
			// 得到一个宽度。
			continue
		}

		CalcSize(f.Type)
		if int32(f.Type.Align) > maxalign {
			maxalign = int32(f.Type.Align)
		}
		if f.Type.Align > 0 {
			o = Rnd(o, int64(f.Type.Align))
		}
		if isStruct { // 对于receiver/args/results，不要设置，它取决于ABI
			f.Offset = o
		}

		w := f.Type.Width
		if w < 0 {
			base.Fatalf("invalid width %d", f.Type.Width)
		}
		if w == 0 {
			lastzero = o
		}
		o += w
		maxwidth := MaxWidth
		// 在32位系统上，反射表施加了额外的约束
		// 每个字段开始偏移量必须适合31位。
		if maxwidth < 1<<32 {
			maxwidth = 1<<31 - 1
		}
		if o >= maxwidth {
			base.ErrorfAt(typePos(errtype), "type %L too large", errtype)
			o = 8 // 小而非零
		}
	}

	// 对于以零大小结尾的非零大小结构，我们添加
	// 类型的额外填充字节。这种填充确保
	// 取零号物体的地址不能制造
	// 指向堆中下一个对象的指针。见第9401期。
	if flag == 1 && o > starto && o == lastzero {
		o++
	}

	// 最后的宽度是四舍五入的
	if flag != 0 {
		o = Rnd(o, int64(maxalign))
	}
	t.Align = uint8(maxalign)

	// 类型宽度仅包括返回到第一个字段的偏移量
	t.Width = o - starto

	return o
}

// findTypeLoop搜索涉及的无效类型声明循环
// 键入t并报告是否找到一个。如果是，则路径包含
// 环
// None
// 路径指向用于跟踪类型序列的切片
// 参观。使用指向片的指针可使片容量
// 增长并限制再分配。
func findTypeLoop(t *Type, path *[]*Type) bool {
	// 我们实现了一个简单的DFS循环查找算法。这
	// 可能更快，但类型周期很少。

	if t.Sym() != nil {
		// 声明的类型。检查是否存在循环或其他问题
		// 在类型中使用的类型表达式上递归
		// 公告

		// 从包导入的类型，因此它不能是
		// 类型循环（否则该包应具有
		// 未能编译）。
		if t.Sym().Pkg != LocalPkg {
			return false
		}

		for i, x := range *path {
			if x == t {
				*path = (*path)[i:]
				return true
			}
		}

		*path = append(*path, t)
		if findTypeLoop(t.Obj().(TypeObject).TypeDefn(), path) {
			return true
		}
		*path = (*path)[:len(*path)-1]
	} else {
		// 匿名类型。在包含的类型上递归。

		switch t.Kind() {
		case TARRAY:
			if findTypeLoop(t.Elem(), path) {
				return true
			}
		case TSTRUCT:
			for _, f := range t.Fields().Slice() {
				if findTypeLoop(f.Type, path) {
					return true
				}
			}
		case TINTER:
			for _, m := range t.Methods().Slice() {
				if m.Type.IsInterface() { // 嵌入式接口
					if findTypeLoop(m.Type, path) {
						return true
					}
				}
			}
		}
	}

	return false
}

func reportTypeLoop(t *Type) {
	if t.Broke() {
		return
	}

	var l []*Type
	if !findTypeLoop(t, &l) {
		base.Fatalf("failed to find type loop for: %v", t)
	}

	// 旋转循环，使最早的类型声明位于第一位。
	i := 0
	for j, t := range l[1:] {
		if typePos(t).Before(typePos(l[i])) {
			i = j + 1
		}
	}
	l = append(l[i:], l[:i]...)

	var msg bytes.Buffer
	fmt.Fprintf(&msg, "invalid recursive type %v\n", l[0])
	for _, t := range l {
		fmt.Fprintf(&msg, "\t%v: %v refers to\n", base.FmtPos(typePos(t)), t)
		t.SetBroke(true)
	}
	fmt.Fprintf(&msg, "\t%v: %v", base.FmtPos(typePos(l[0])), l[0])
	base.ErrorfAt(typePos(l[0]), msg.String())
}

// CalcSize计算并存储t的大小和对齐方式。
// 如果设置了CalcSizeDisabled，并且
// 尚未计算，则称为致命。
// 这用于防止后端的数据争用。
func CalcSize(t *Type) {
	// 启用类型检查跟踪时调用CalcSize不安全。
	// 见第33658期。
	if base.EnableTrace && SkipSizeForTracing {
		return
	}
	if PtrSize == 0 {
		// 假设这是一个测试。
		return
	}

	if t == nil {
		return
	}

	if t.Width == -2 {
		reportTypeLoop(t)
		t.Width = 0
		t.Align = 1
		return
	}

	if t.WidthCalculated() {
		return
	}

	if CalcSizeDisabled {
		if t.Broke() {
			// 从下面的致命调用中断无限递归
			return
		}
		t.SetBroke(true)
		base.Fatalf("width not calculated: %v", t)
	}

	// 如果断开的递归类型
	// 再次引用
	if t.Broke() && t.Width == 0 {
		return
	}

	// 将CheckSize呼叫推迟到我们完成之后
	DeferCheckSize()

	lno := base.Pos
	if pos := t.Pos(); pos.IsKnown() {
		base.Pos = pos
	}

	t.Width = -2
	t.Align = 0 // 0表示使用t.宽度，如下所示

	et := t.Kind()
	switch et {
	case TFUNC, TCHAN, TMAP, TSTRING:
		break

	// 在引导过程中SimType==0
	default:
		if SimType[t.Kind()] != 0 {
			et = SimType[t.Kind()]
		}
	}

	var w int64
	switch et {
	default:
		base.Fatalf("CalcSize: unknown type: %v", t)

	// 特定于编译器的东西
	case TINT8, TUINT8, TBOOL:
		// 布尔是int8
		w = 1

	case TINT16, TUINT16:
		w = 2

	case TINT32, TUINT32, TFLOAT32:
		w = 4

	case TINT64, TUINT64, TFLOAT64:
		w = 8
		t.Align = uint8(RegSize)

	case TCOMPLEX64:
		w = 8
		t.Align = 4

	case TCOMPLEX128:
		w = 16
		t.Align = uint8(RegSize)

	case TPTR:
		w = int64(PtrSize)
		CheckSize(t.Elem())

	case TUNSAFEPTR:
		w = int64(PtrSize)

	case TINTER: // 实现为2个指针
		w = 2 * int64(PtrSize)
		t.Align = uint8(PtrSize)
		expandiface(t)

	case TCHAN: // 作为指针实现
		w = int64(PtrSize)

		CheckSize(t.Elem())

		// 制作假字体，以便稍后进行检查
		// 触发通道参数检查。
		t1 := NewChanArgs(t)
		CheckSize(t1)

	case TCHANARGS:
		t1 := t.ChanArgs()
		CalcSize(t1) // 以防万一
		if t1.Elem().Width >= 1<<16 {
			base.ErrorfAt(typePos(t1), "channel element type too large (>64kB)")
		}
		w = 1 // 什么都行

	case TMAP: // 作为指针实现
		w = int64(PtrSize)
		CheckSize(t.Elem())
		CheckSize(t.Key())

	case TFORW: // 应该填写的
		reportTypeLoop(t)
		w = 1 // 什么都行

	case TANY:
		// 不是真正的类型；使用前应更换。
		base.Fatalf("CalcSize any")

	case TSTRING:
		if StringSize == 0 {
			base.Fatalf("early CalcSize string")
		}
		w = StringSize
		t.Align = uint8(PtrSize)

	case TARRAY:
		if t.Elem() == nil {
			break
		}

		CalcSize(t.Elem())
		if t.Elem().Width != 0 {
			cap := (uint64(MaxWidth) - 1) / uint64(t.Elem().Width)
			if uint64(t.NumElem()) > cap {
				base.ErrorfAt(typePos(t), "type %L larger than address space", t)
			}
		}
		w = t.NumElem() * t.Elem().Width
		t.Align = t.Elem().Align

	case TSLICE:
		if t.Elem() == nil {
			break
		}
		w = SliceSize
		CheckSize(t.Elem())
		t.Align = uint8(PtrSize)

	case TSTRUCT:
		if t.IsFuncArgStruct() {
			base.Fatalf("CalcSize fn struct %v", t)
		}
		w = calcStructOffset(t, t, 0, 1)

	// 制作假字体，以便稍后进行检查
	// 触发器函数参数计算。
	case TFUNC:
		t1 := NewFuncArgs(t)
		CheckSize(t1)
		w = int64(PtrSize) // func类型的宽度是指针

	// 功能分为3种结构；
	// 计算它们的宽度作为副作用。
	case TFUNCARGS:
		t1 := t.FuncArgs()
		w = calcStructOffset(t1, t1.Recvs(), 0, 0)
		w = calcStructOffset(t1, t1.Params(), w, RegSize)
		w = calcStructOffset(t1, t1.Results(), w, RegSize)
		t1.Extra.(*Func).Argwid = w
		if w%int64(RegSize) != 0 {
			base.Warn("bad type %v %d\n", t1, w)
		}
		t.Align = 1

	case TTYPEPARAM:
		// TODO（danscales）-在我们消除需求时删除
		// 在noder2中执行CalcSize（在noder中不需要）
		w = int64(PtrSize)
	}

	if PtrSize == 4 && w != int64(int32(w)) {
		base.ErrorfAt(typePos(t), "type %v too large", t)
	}

	t.Width = w
	if t.Align == 0 {
		if w == 0 || w > 8 || w&(w-1) != 0 {
			base.Fatalf("invalid alignment for %v", t)
		}
		t.Align = uint8(w)
	}

	base.Pos = lno

	ResumeCheckSize()
}

// CalcStructSize计算s的大小，
// 填充s.宽度和s.对齐，
// 即使尺寸计算被禁用。
func CalcStructSize(s *Type) {
	s.Width = calcStructOffset(s, s, 0, 1) // 集合对齐
}

// 当一个类型的宽度应该已知时，我们称之为CheckSize
// 计算它。在一个像
// None
// 键入T*struct{next T}
// None
// 有必要推迟结构宽度的计算
// 直到T被初始化为指向该结构的指针。
// 类似地，在导入处理期间，可以使用结构
// 在他们的定义之前。在这种情况下，打电话
// DeferCheckSize（）停止宽度计算，直到
// 调用ResumeCheckSize（），此时所有
// 将执行延迟的CalcSize。
// 仅当类型的大小为
// 这是急需的。CheckSize确保
// 最终评估尺寸。

var deferredTypeStack []*Type

func CheckSize(t *Type) {
	if t == nil {
		return
	}

	// 不应检查函数arg结构
	// 在封闭函数的外部。
	if t.IsFuncArgStruct() {
		base.Fatalf("CheckSize %v", t)
	}

	if defercalc == 0 {
		CalcSize(t)
		return
	}

	// 如果尚未将类型推送到deferredTypeStack上，请立即执行
	if !t.Deferwidth() {
		t.SetDeferwidth(true)
		deferredTypeStack = append(deferredTypeStack, t)
	}
}

func DeferCheckSize() {
	defercalc++
}

func ResumeCheckSize() {
	if defercalc == 1 {
		for len(deferredTypeStack) > 0 {
			t := deferredTypeStack[len(deferredTypeStack)-1]
			deferredTypeStack = deferredTypeStack[:len(deferredTypeStack)-1]
			t.SetDeferwidth(false)
			CalcSize(t)
		}
	}

	defercalc--
}

// PtrDataSize返回t前缀的长度（字节）
// 包含指针数据的。此偏移量之后的任何内容都是标量数据。
func PtrDataSize(t *Type) int64 {
	if !t.HasPointers() {
		return 0
	}

	switch t.Kind() {
	case TPTR,
		TUNSAFEPTR,
		TFUNC,
		TCHAN,
		TMAP:
		return int64(PtrSize)

	case TSTRING:
		// 结构{byte*str；intgo len；}
		return int64(PtrSize)

	case TINTER:
		// 结构{Itab*选项卡；void*数据；}或
		// 结构{Type*Type；void*data；}
		// 注：请参见字体位中的注释。设置
		return 2 * int64(PtrSize)

	case TSLICE:
		// 结构{byte*数组；uintgo len；uintgo cap；}
		return int64(PtrSize)

	case TARRAY:
		// haspointers已删除t.NumElem（）==0。
		return (t.NumElem()-1)*t.Elem().Width + PtrDataSize(t.Elem())

	case TSTRUCT:
		// 查找具有指针的最后一个字段。
		var lastPtrField *Field
		fs := t.Fields().Slice()
		for i := len(fs) - 1; i >= 0; i-- {
			if fs[i].Type.HasPointers() {
				lastPtrField = fs[i]
				break
			}
		}
		return lastPtrField.Offset + PtrDataSize(lastPtrField.Type)

	default:
		base.Fatalf("PtrDataSize: unexpected type, %v", t)
		return 0
	}
}
